1. Field of the Invention
This invention generally relates to wireless ad-hoc and sensor networks and in particular to a method, device and computer program product configured to select forward wireless nodes for data packet rebroadcast in network wide broadcasting.
2. Discussion of the Background
To broadcast a packet throughout an entire ad-hoc or sensor network including a plurality of nodes (e.g., wireless nodes) while multi-hopping from one node to another, all or some nodes need to rebroadcast the packet. Further, in a network with a dynamic topography, including a plurality of nodes that may be mobile and/or nodes that are added and removed from a network, it is impractical to determine statically which nodes should forward broadcast packets to their neighbors.
A simple approach is flooding, in which every node rebroadcasts the data packet exactly one time upon receiving it. Simple flooding causes a number of broadcasts as high as a number of nodes in a network. Therefore, it is not a desired solution due to traffic overhead generated within the network. S. Ni, Y. Tsing, Y. Chen, and J. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” MobiCom, 1999, which is incorporated by reference herein in its entirety, pointed out the “broadcast storm problem” when every device forwards the packet once and recommends several approaches to reduce the number of forward nodes so that every node can still receive the broadcast packet:
A probabilistic scheme allows forwarding with a pre-specified probability p. A counter based scheme forwards a packet only if the number of duplicated broadcast packets received during a waiting interval is less than a threshold. If position information is available, a location based scheme only forwards when the additional coverage area is larger than a threshold. B. Williams and T. Camp, “Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks,” MobiHoc, 2002, which is incorporated by reference herein in its entirety, compared these schemes to many other approaches.
The knowledge of network topology can be employed to make a better decision on selecting forward nodes. H. Lim and C. Kim, “Flooding in Wireless Ad Hoc Networks,” Computer Communication Journal, 24(3-4): 353-363, 2001, which is incorporated by reference herein in its entirety, stated that if the global network topology information is known, the problem of selecting the minimum number of forward nodes is NP-complete. But the optimal solution can be approximated with a constant ratio if position information is available.
If only local network topology information is available, such as a list of 1-hop or 2-hop neighbors, two major approaches are used to select forward nodes. In a self-pruning scheme, a node itself decides whether to forward or not, as described in F. Dai and J. Wu, “Performance Analysis of Broadcast Protocols in Ad Hoc Networks Based on Self-Pruning,” IEEE Trans. on Parallel and Distributed Systems, to appear, 2004, which is incorporated by reference herein in its entirety. In a neighbor-designation scheme, as suggested in W. Lou and J. Wu, “Localized Broadcasting in Mobile Ad Hoc Networks Using Neighbor Designation,” Handbook of Mobile Computing, CRC Press, 2004, which is incorporated by reference herein in its entirety, a node is assigned a subset of its neighbors to rebroadcast. To get 2-hop neighbor information, Lou and Wu assume that nodes exchange “Hello” messages with their 1-hop neighbors. These “Hello” messages contain the number of 1-hop neighbors.
Energy efficiency in broadcast has been extensively studied. For example, M. Cagalj, J. Hubaux, and C. Enz, “Minimum-Energy Broadcast in All-Wireless Networks: NP-Completeness and Distribution Issues,” MobiCom 2002, which is incorporated by reference herein in its entirety, proposed a centralized algorithm. However, for their centralized algorithm to find a minimum energy broadcast tree is a NP-complete problem. On the other hand, local algorithms such as described by J. Cartigny, D. Simplot, and I. Stojmenovic, “Localized Minimum-Energy Broadcasting in Ad-Hoc Networks,” InfoCom 2003, which is incorporated by reference herein in its entirety, need position information and controlled power, and may not be able to closely approximate the optimal solution either.
FIG. 11 shows an example of a node 1100 operating according to these background methods. The node 1100 includes a physical and MAC layer 1140 that receives packets 1150 transmitted from other devices in the network. Each received packet 1150 includes a message 1115 and source address 1125. If the received packet 1150 is a data broadcast packet, the received packet 1150 also includes a list of forwarding nodes 1170. The physical and MAC layer 1140 passes the received packet 1150 to the networking layer 1120, and the networking layer 1120 determines a forwarding strategy for the received packet 1150. The networking layer 1120 also forms a new packet 1160 that includes a list of new forwarding nodes 1180 and new source address 1135. The new packet 1160 is then broadcast by the physical and MAC layer 1140.
FIG. 12 shows a detailed view of a background networking layer 1120, which performs forward node selection and creation of a forward node list 1180. Node 1100 maintains a 1-hop neighbor table 1200 at the networking layer 1120. The 1-hop neighbor table 1200 includes, for each neighbor of the device, a neighbor addresses 1220, a full list of 1-hop neighbor addresses 1230 (i.e., list of addresses of 1-hop neighbors of the neighbor) and a broadcast flag 1240.
In the background method, every node 1100 updates the full 1-hop neighbor list 1230 for each neighbor 1220 by exchanging a “Hello” message 1215 with neighbor 1220. However, the neighbor table exchanging disadvantageously introduces excess traffic into the network, because messages are exchanged between every pair of nodes in the network. In particular, the Forward Node List Creation Unit 1260 uses every Neighbor ID 1220, 1-hop neighbor list 1230 and Broadcast Flag 1240 in the 1-hop neighbor table 1200 to determine the list of forwarding nodes 1180, which is to be inserted into the rebroadcast packet 1160. As a result, the background method produces excess traffic for exchanging full neighbor information. Further, background methods with excess traffic are energy inefficient because every transmitted bit consumes power, and this is especially significant for nodes that operate from a battery power source.